'''
地上有一个m行n列的方格，从坐标 [0,0] 到坐标 [m-1,n-1] 。
一个机器人从坐标 [0, 0] 的格子开始移动，它每次可以向左、右、上、下移动一格（不能移动到方格外），
也不能进入行坐标和列坐标的数位之和大于k的格子。例如，当k为18时，机器人能够进入方格 [35, 37] ，因为3+5+3+7=18。
但它不能进入方格 [35, 38]，因为3+5+3+8=19。请问该机器人能够到达多少个格子？
'''
# 数位之和计算：
# 设一数字 xx ，向下取整除法符号 //// ，求余符号 ⊙ ，则有：
# x⊙10 ：得到 xx 的个位数字；
# x//10 ： 令 xx 的十进制数向右移动一位，即删除个位数字。
#  当 n m 不定范围的时候，直接用通用的数位和公式就行，本题使用增量公式只是为了进一步减少计算量~~
def sums(x):
    s = 0
    while x != 0:
        s += x % 10
        x = x // 10
    return s

# 机器人移动的增量！
# s_x + 1 if (x + 1) % 10 else s_x - 8
class Solution:
    def movingCount(self, m: int, n: int, k: int) -> int:
        def dfs(i, j, sumi, sumj):
            if i >= m or j >= n or k < sumi + sumj or (i, j) in visited: return 0
            visited.add((i,j))
            return 1 + dfs(i + 1, j, sumi + 1 if (i + 1) % 10 else sumi - 8, sumj) + dfs(i, j + 1, sumi, sumj + 1 if (j + 1) % 10 else sumj - 8)
        visited = set()
        return dfs(0, 0, 0, 0)
# 增量公式！思想是一致的！

# 遍历的做法 dfs
# -*- coding:utf-8 -*-
class Solution:
    def movingCount(self, threshold, rows, cols):
        # write code here
        num = 0
        for i in range(rows):
            for j in range(cols):
                if(self.calSum(i) + self.calSum(j) <= threshold):
                    num = num + 1
                elif(rows==1 or cols==1):
                    return num
        return num

    def calSum(self, temp):
        sum = 0
        while(temp != 0):
            # 取余 取个位数
            sum += temp % 10
            # 整除 取高位数 个位数temp = 0
            temp = temp // 10
        return sum